import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
//        int arr[] = new int[]{3,2,4,7,5,8,6,9};
//        double x = avg(arr);
//        System.out.println("数组中所有元素的平均值为：" + x);

//        double x = sum(arr);
//        System.out.println("数组所有元素之和" + x);

//        int arr[] = new int[]{1,2,3};
//        transform(arr);
//        String sArr = Arrays.toString(arr);
//        System.out.println(sArr);

//        int arr[] = new int[]{3,2,4,7,5,8,6,9};
//        printArray(arr);

//        int arr[] = new int[100];
//        arrInit(arr);
//        String sArr = Arrays.toString(arr);
//        System.out.println(sArr);

//        int arr[] = new int[]{2,4,1,1,6,33,1,5,6,7,6};
//        if(checkThreeNum(arr)){
//            System.out.println("存在");
//        }else{
//            System.out.println("不存在");
//        }

        int arr[] = new int[]{7,7,5,6,6,6,6,6,6,7,7};
        int n = judgeMajority3(arr);
        System.out.println("多数元素是：" + n);

//        int arr[] = new int[]{1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,9};
//        int single = findSingleDog(arr);
//        System.out.println("单身狗是：" + single);

//        int arr[] = new int[]{0,2,3,8,9,14,24,57,369};
//        int subs[] = findSubscript(arr,22);
//        String sSubs = Arrays.toString(subs);
//        System.out.println("下标是：" + sSubs);

//        int arr[] = new int[]{3,2,5,8,4,7,6,9};
//        bubbleSort(arr);
//        String sArr = Arrays.toString(arr);
//        System.out.println("排序结果为：" + sArr);

//        int arr[] = new int[]{1,2,4,5,7,8,9};
//        if(judgeOrder(arr)){
//            System.out.println("是升序");
//        } else{
//            System.out.println("不是升序");
//        }

//        int[] arr = new int[]{1,3,5,7,8,15,24,33,56};
//        int x = dichotomy(arr,24);
//        if(x == -1){
//            System.out.println("未找到");
//        }else {
//            System.out.println(arr[x]);
//        }

//        int arr[] = new int[]{3,2,5,8,4,7,6,9};
//        int newArr[] = myCopyOf(arr,arr.length);
//        String sArr = Arrays.toString(newArr);
//        System.out.println("新数组为：" + sArr);

//        int arr[] = new int[]{3,2,5,8,4,7,6,9};
//        String sArr = myToString(arr);
//        System.out.println(sArr);
    }


    //14.实现一个方法 toString, 把一个整型数组转换成字符串.
    // 例如数组 {1, 2, 3} , 返回的字符串为 "[1, 2, 3]", 注意 逗号 的位置和数量.
    public static String myToString(int[] arr) {
        String sArr = "[";
        for (int i = 0; i < arr.length; i++) {
            sArr = sArr + arr[i];
            if(i != arr.length - 1){
                sArr = sArr + ", ";
            }
        }
        sArr += "]";
        return sArr;
    }

    //13.实现一个方法 copyOf, 对一个整型数组进行拷贝, 得到一个新的数组.
    public static int[] myCopyOf(int[] arr, int length) {
        int newArr[] = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            newArr[i] = arr[i];
        }
        return newArr;
    }

    //12.给定一个有序整型数组, 实现二分查找
    public static int dichotomy(int[] arr,int target) {
        int start = 0;
        int end = arr.length - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(target < arr[mid]){
                end = mid - 1;
            }else if(target > arr[mid]){
                start = mid + 1;
            } else{
              return mid;
            }
        }
        return -1;
    }

    //11.给定一个整型数组, 判定数组是否有序（递增）
    public static boolean judgeOrder(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if(arr[i] > arr[i + 1])
                return false;
        }
        return true;
    }

    //10.给定一个整型数组, 实现冒泡排序(升序排序)
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j + 1]){
                    int temp = 0;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    //9.给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
    public static int[] findSubscript(int[] arr,int target) {
        int[] subs = new int[2];
        int start = 0;
        int end = arr.length - 1;
        while(start < end){
            if(arr[start] + arr[end] < target){
                start++;
            }else if(arr[start] + arr[end] > target){
                end--;
            }else{
                subs[0] = start;
                subs[1] = end;
                break;
            }
        }
        return subs;
    }

    //8.给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    public static int findSingleDog(int[] arr) {
        int x = 0;
        for (int i = 0; i < arr.length; i++) {
            x ^= arr[i];
        }
        return x;
    }

    //7.给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
    public static int judgeMajority1(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > max){
                max = arr[i];
            }
            if(arr[i] < min){
                min = arr[i];
            }
        }
        int n = max - min + 1;
        int newArr[] = new int[n];
        for (int i = 0; i < arr.length; i++) {
            newArr[arr[i] - min]++;
        }
        int x = 0;
        for (int i = 0; i < n; i++) {
            if(newArr[i] > arr.length / 2)
                x = i + min;
        }
        return x;
    }

    public static int judgeMajority2(int[] arr) {
        int count = 0;
        int majority = arr[0];

        for (int i : arr) {
            if (count == 0) {
                majority = arr[i];
            }
            if (arr[i] == majority) {
                count++;
            } else {
                count--;
            }
        }
        return majority;
    }

    public static int judgeMajority3(int[] arr) {
        return majority(arr,0,arr.length - 1);
    }

    public static int majority(int[] arr, int left, int right) {
        if(left == right){
            return arr[left];
        }
        int mid = (left + right) / 2;
        int leftNum = majority(arr,left,mid);
        int rightNum = majority(arr,mid + 1,right);
        if(leftNum == rightNum){
            return leftNum;
        }

        //如果左右两边的众数不一样,返回出现次数多的那一个
        int leftCount = count(leftNum,arr,left,mid);
        int rightCount = count(rightNum,arr,mid + 1,right);
        return leftCount > rightCount ? leftNum : rightNum;
    }

    //在区间中num出现的次数
    public static int count(int num, int[] arr, int start, int end) {
        int count = 0;
        for (int i = start; i <= end; i++) {
            if(num == arr[i]){
                count++;
            }
        }
        return count;
    }


//    public static int judgeMajority2(int[] arr) {
//        int count = 0;
//        int majority = arr[0];
//        for (i:arr) {
//            if(count == 0){
//                majority = arr[i];
//            }
//            if(arr[i] == majority){
//                count++;
//            }
//            else{
//                coun--;
//            }
//        }
//        return majority;
//    }

    //6.给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。
    public static boolean checkThreeNum(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] % 2 == 1){
                count++;
            } else{
                count = 0;
            }
            if(count == 3){
                return true;
            }
        }
        return false;
    }

    //5.创建一个 int 类型的数组, 元素个数为 100, 并把每个元素依次设置为 1 - 100
    public static void arrInit(int[] arr) {
        for (int i = 1; i <= arr.length; i++) {
            arr[i - 1] = i;
        }
    }

    //4.实现一个方法 printArray, 以数组为参数, 循环访问数组中的每个元素, 打印每个元素的值.
    public static void printArray(int[] arr) {
        System.out.println("数组每个元素的值：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    //3.实现一个方法 transform, 以数组为参数, 循环将数组中的每个元素 乘以 2
    // 并设置到对应的数组元素上. 例如 原数组为 {1, 2, 3}, 修改之后为 {2, 4, 6}
    public static void transform(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i] * 2;
        }
    }

    //2.实现一个方法 sum, 以数组为参数, 求数组所有元素之和.
    public static double sum(int[] arr) {
        double x = 0.0;
        for (int i = 0; i < arr.length; i++) {
            x += arr[i];
        }
        return x;
    }

    //1.实现一个方法 avg, 以数组为参数, 求数组中所有元素的平均值(注意方法的返回值类型).
    public static double avg(int[] arr) {
        double sum = 0.0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        return sum / arr.length;
    }
}
